Shortest Word Distance

Time: O(N); Space: O(1); easy

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Example 1:

Input: words = [“practice”, “makes”, “perfect”, “coding”, “makes”], word1=“coding”, word2=“practice”

Output: 3

Example 1:

Input: words = [“practice”, “makes”, “perfect”, “coding”, “makes”], word1=“makes”, word2=“coding”

Output: 1

Note:

  • You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

[3]:

class Solution1(object):
    def shortestDistance(self, words, word1, word2):
        """
        :type words List[string]
        :type word1 string
        :type word2 string
        :rtype: int
        """
        dist = float("inf")
        i, index1, index2 = 0, None, None

        while i < len(words):
            if words[i] == word1:
                index1 = i
            elif words[i] == word2:
                index2 = i

            if index1 is not None and index2 is not None:
                dist = min(dist, abs(index1 - index2))
            i += 1

        return dist

[4]:

s = Solution1()
words = ["practice", "makes", "perfect", "coding", "makes"]
word1="coding"
word2="practice"
assert s.shortestDistance(words, word1, word2) == 3
word1="makes"
word2="coding"
assert s.shortestDistance(words, word1, word2) == 1